package com.xiaolin.algorithm.greed;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @ClassName IntervalScheduling
 * @Description 区间调度问题
 * @Detail 使用贪心算法，其实贪心算法是动态规划算法的一个特例，其性能比动态规划好，都是限制比动态规划多，所以应用没有动态规划广泛
 * @Author MyPC
 * @Date 2020/11/21
 * @Version 1.0
 */
public class IntervalScheduling {

    public static void main(String[] args) {
        int[][] ints=new int[][]{{1,3},{2,4},{3,8},{12,16}};
        System.out.println(findIntervals(ints));
        System.out.println(removeIntervals(ints));
        System.out.println(shootBalloon(ints));
    }

    /**
     * 要求： 找出有多少不重合的区间
     * 思路：
     *      1、找出最早闭合的区间
     *      2、找出离选中的闭合的区间最近的但没有交集的区间
     *      3、选中找到的区间
     *      3、重复1、2步骤，直到结束
     * @param intervals  区间数组  如[[1,3],[2,4],[3,8]]
     * @return
     */
    public static int findIntervals(int[][] intervals) {
        //对区间end由从小到大排序
        sort(intervals);
        // 区间end，先取第一个区间
        int end=intervals[0][1];
        // 不重合的区间数
        int count=1;
        for(int i=1;i<intervals.length;i++){
            if(end <= intervals[i][0]){
                // 区间不重合
                //计数加1
                count++;
                // 从小选择区间end
                end=intervals[i][1];
            }
        }
        // 不重合的区间要么0个，要么大于1个
        return count!=1 ? count: 0;
    }


    /**
     * 要求：给定一个区间数组，找到需要移除的区间的最少数量，使剩下的区间互不重叠
     * 思路：
     *      区间数组长度-已找出的不重合的区间数量
     * @param intervals
     * @return
     */
    public static int removeIntervals(int[][] intervals){
        //对区间进行排序
        sort(intervals);
        return intervals.length-findIntervals(intervals);
    }

    /**
     *  射气球，要求用最少的箭射爆所有气球
     *  思路：
     *      1、有多少不重叠的区间，就需要多少箭，与求不重叠区间不同的是，这里闭合end与起始start相等也算重合
     * @param intervals
     * @return
     */
    public static int shootBalloon(int[][] intervals){
        // 排序
        sort(intervals);
        // 所需的箭数量,至少需要1支
        int arrows=1;
        int end=intervals[0][1];
        for(int i=1;i<intervals.length;i++){
            if(end<intervals[i][0]){
                // 不重合
                // 箭数+1
                arrows++;
                //闭合end指向新的区间
                end=intervals[i][1];
            }
        }
        return arrows;
    }



    /**
     * 排序二维数组
     * @param intervals
     */
    public static void sort(int[][] intervals){
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                // 升序
                if(o1[1] > o2[1]){
                    return 1;
                }else if(o1[1] < o2[1]){
                    return -1;
                }
                return 0;
            }
        });
    }
}
